package cn.itcast.algorithm.exercise;

import cn.itcast.algorithm.exercise.helpclass.ListNode;
import org.junit.Test;

import java.util.List;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class ExerciseAB11 {
    @Test
    public void exerciseAB11Test() {
        ListNode list1 = new ListNode(1) ;
        ListNode data11 = new ListNode(3) ;
        ListNode data12 = new ListNode(5) ;
        list1.next = data11 ;
        data11.next = data12 ;

        ListNode list2 = new ListNode(1) ;
        ListNode data21 = new ListNode(3) ;
        ListNode data22 = new ListNode(5) ;
        list2.next = data21 ;
        data21.next = data22 ;

        System.out.println(list1+"<<>>"+list2);

        ListNode newHead = mergeList(list1, list2) ;

        System.out.println(newHead);
    }

    /**
     * 合并有序队列 空间复杂度O(1) 时间复杂度O(N)
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeList(ListNode list1, ListNode list2) {
        // 考核在不使用额外空间的情况下 针对其中一个链表的插入操作
        if (list1 == null && list2 == null) {
            return list1 ;
        }

        if (list1 == null) {
            return list2 ;
        }

        if (list2 == null) {
            return list1 ;
        }

        // 处理临界点(以小的那个list为基准)
        if (list1.val > list2.val) {
            ListNode tmpNode = list1 ;
            list1 = list2 ;
            list2 = tmpNode ;
        }

        if (list1.next == null) {
            list1.next = list2 ;
            return list1 ;
        }

        // 以list1为基准 执行链表增发
        ListNode head1 = list1 ;
        while(list1.next != null) {
            ListNode preNode = list1 ;
            ListNode nextNode = list1.next ;
            ListNode insertNode = list2 ;

            if (list2 == null) {
                break;
            }

            if (preNode.val >= insertNode.val) {
                list2 = list2.next ;
                insertNode.next = preNode.next ;
                list1.next = insertNode ;
            }else if (preNode.val < insertNode.val && insertNode.val <= nextNode.val) {
                list2 = list2.next ;
                insertNode.next = nextNode ;
                preNode.next = insertNode ;
            }

            if (list1.next == null) {
                list1.next = list2 ;
                break;
            }else {
                list1 = list1.next ;
            }
        }

        // 最后一个元素特殊处理
        if (list2 != null) {
            list1.next = list2 ;
        }

        return head1 ;
    }
}
